﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace MoPhongThuatToan
{
    class Prim:CANHNA
    {
        private int n;
        private int[,] a = new int[100, 100];
        private CANHNA[] T = new CANHNA[10000];
        private int nT;
        private int[] nhan = new int[10000];
        public void NhapFile(String FilePath)
        {
            FileStream fs = new FileStream(FilePath, FileMode.Open);
            StreamReader sr = new StreamReader(fs);
            n = Convert.ToInt32(sr.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string Line = sr.ReadLine();
                string[] G = Line.Split(new char[] { ' ' });
                for (int j = 0; j < n; j++)
                {
                    a[i, j] = int.Parse(G[j]);
                }
            }
            sr.Close();
            fs.Close();
        }
        public void XuatFile(string FilePath)
        {
            FileStream fs = new FileStream(FilePath, FileMode.Create);
            StreamWriter sw = new StreamWriter(fs);
            sw.WriteLine(n);
            //for (int i = 0; i < n; i++)
            //{
            //    for (int j = 0; j < n; j++)
            //    {
            //        sw.Write(a[i, j]);
            //        sw.Write("\t");
            //    }
            //    sw.Write("\n");
            //    sw.Write(sw.NewLine);
            //}
            PrimAlg();
            int temp = 0;
            for (int i = 0; i < nT; i++)
            {
                temp += T[i].GetTS();
                sw.Write(T[i].GetDinh1());
                sw.Write("==>");
                sw.Write(T[i].GetDinh2());
                sw.Write("\n");
            }
            sw.Write(temp);
            sw.Close();
            fs.Close();
        }
        public void PrimAlg()
        {
            nT = 0;
            for (int i = 0; i < n; i++)
                nhan[i] = 0;
            nhan[0] = 1;
            while (nT < n - 1)
            {
                CANHNA emin=new CANHNA();
                int nmin;
                nmin = -1;
                for (int w = 0; w < n; w++)
                {
                    if (nhan[w] == 0)
                    {
                        for (int v = 0; v < n; v++)
                        {
                            if (nhan[v] == 1 && a[w, v] != 0)
                            {
                                if (nmin == -1 || a[w, v] < nmin)
                                {
                                    nmin = a[w, v];
                                    emin.SetDinh2(w);
                                    emin.SetDinh1(v);

                                    emin.SetTS(nmin);
                                }
                            }
                        }
                    }
                }
                T[nT] = emin;
                nT++;
                nhan[emin.GetDinh2()] = 1;
            }
        }
    }
}
